YES 1.19 H-Termination proof of /home/matraf/haskell/eval_FullyBlown_Fast/FiniteMap.hs
H-Termination of the given Haskell-Program with start terms could successfully be proven:



HASKELL
  ↳ LR

mainModule FiniteMap
  ((eltsFM_GE :: FiniteMap Ordering a  ->  Ordering  ->  [a]) :: FiniteMap Ordering a  ->  Ordering  ->  [a])

module FiniteMap where
  import qualified Maybe
import qualified Prelude

  data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b


  instance (Eq a, Eq b) => Eq (FiniteMap b a) where 

  eltsFM_GE :: Ord b => FiniteMap b a  ->  b  ->  [a]
eltsFM_GE fm fr foldFM_GE (\key elt rest ->elt : rest) [] fr fm

  foldFM_GE :: Ord b => (b  ->  c  ->  a  ->  a ->  a  ->  b  ->  FiniteMap b c  ->  a
foldFM_GE k z fr EmptyFM z
foldFM_GE k z fr (Branch key elt _ fm_l fm_r
 | key >= fr = 
foldFM_GE k (k key elt (foldFM_GE k z fr fm_r)) fr fm_l
 | otherwise = 
foldFM_GE k z fr fm_r


module Maybe where
  import qualified FiniteMap
import qualified Prelude



Lambda Reductions:
The following Lambda expression
\keyeltrestelt : rest

is transformed to
eltsFM_GE0 key elt rest = elt : rest



↳ HASKELL
  ↳ LR
HASKELL
      ↳ BR

mainModule FiniteMap
  ((eltsFM_GE :: FiniteMap Ordering a  ->  Ordering  ->  [a]) :: FiniteMap Ordering a  ->  Ordering  ->  [a])

module FiniteMap where
  import qualified Maybe
import qualified Prelude

  data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a


  instance (Eq a, Eq b) => Eq (FiniteMap b a) where 

  eltsFM_GE :: Ord a => FiniteMap a b  ->  a  ->  [b]
eltsFM_GE fm fr foldFM_GE eltsFM_GE0 [] fr fm

  
eltsFM_GE0 key elt rest elt : rest

  foldFM_GE :: Ord b => (b  ->  c  ->  a  ->  a ->  a  ->  b  ->  FiniteMap b c  ->  a
foldFM_GE k z fr EmptyFM z
foldFM_GE k z fr (Branch key elt _ fm_l fm_r
 | key >= fr = 
foldFM_GE k (k key elt (foldFM_GE k z fr fm_r)) fr fm_l
 | otherwise = 
foldFM_GE k z fr fm_r


module Maybe where
  import qualified FiniteMap
import qualified Prelude



Replaced joker patterns by fresh variables and removed binding patterns.

↳ HASKELL
  ↳ LR
    ↳ HASKELL
      ↳ BR
HASKELL
          ↳ COR

mainModule FiniteMap
  ((eltsFM_GE :: FiniteMap Ordering a  ->  Ordering  ->  [a]) :: FiniteMap Ordering a  ->  Ordering  ->  [a])

module FiniteMap where
  import qualified Maybe
import qualified Prelude

  data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a


  instance (Eq a, Eq b) => Eq (FiniteMap b a) where 

  eltsFM_GE :: Ord b => FiniteMap b a  ->  b  ->  [a]
eltsFM_GE fm fr foldFM_GE eltsFM_GE0 [] fr fm

  
eltsFM_GE0 key elt rest elt : rest

  foldFM_GE :: Ord a => (a  ->  b  ->  c  ->  c ->  c  ->  a  ->  FiniteMap a b  ->  c
foldFM_GE k z fr EmptyFM z
foldFM_GE k z fr (Branch key elt vw fm_l fm_r
 | key >= fr = 
foldFM_GE k (k key elt (foldFM_GE k z fr fm_r)) fr fm_l
 | otherwise = 
foldFM_GE k z fr fm_r


module Maybe where
  import qualified FiniteMap
import qualified Prelude



Cond Reductions:
The following Function with conditions
foldFM_GE k z fr EmptyFM = z
foldFM_GE k z fr (Branch key elt vw fm_l fm_r)
 | key >= fr
 = foldFM_GE k (k key elt (foldFM_GE k z fr fm_r)) fr fm_l
 | otherwise
 = foldFM_GE k z fr fm_r

is transformed to
foldFM_GE k z fr EmptyFM = foldFM_GE3 k z fr EmptyFM
foldFM_GE k z fr (Branch key elt vw fm_l fm_r) = foldFM_GE2 k z fr (Branch key elt vw fm_l fm_r)

foldFM_GE0 k z fr key elt vw fm_l fm_r True = foldFM_GE k z fr fm_r

foldFM_GE1 k z fr key elt vw fm_l fm_r True = foldFM_GE k (k key elt (foldFM_GE k z fr fm_r)) fr fm_l
foldFM_GE1 k z fr key elt vw fm_l fm_r False = foldFM_GE0 k z fr key elt vw fm_l fm_r otherwise

foldFM_GE2 k z fr (Branch key elt vw fm_l fm_r) = foldFM_GE1 k z fr key elt vw fm_l fm_r (key >= fr)

foldFM_GE3 k z fr EmptyFM = z
foldFM_GE3 wv ww wx wy = foldFM_GE2 wv ww wx wy

The following Function with conditions
compare x y
 | x == y
 = EQ
 | x <= y
 = LT
 | otherwise
 = GT

is transformed to
compare x y = compare3 x y

compare1 x y True = LT
compare1 x y False = compare0 x y otherwise

compare0 x y True = GT

compare2 x y True = EQ
compare2 x y False = compare1 x y (x <= y)

compare3 x y = compare2 x y (x == y)

The following Function with conditions
undefined 
 | False
 = undefined

is transformed to
undefined  = undefined1

undefined0 True = undefined

undefined1  = undefined0 False



↳ HASKELL
  ↳ LR
    ↳ HASKELL
      ↳ BR
        ↳ HASKELL
          ↳ COR
HASKELL
              ↳ Narrow

mainModule FiniteMap
  (eltsFM_GE :: FiniteMap Ordering a  ->  Ordering  ->  [a])

module FiniteMap where
  import qualified Maybe
import qualified Prelude

  data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b


  instance (Eq a, Eq b) => Eq (FiniteMap a b) where 

  eltsFM_GE :: Ord b => FiniteMap b a  ->  b  ->  [a]
eltsFM_GE fm fr foldFM_GE eltsFM_GE0 [] fr fm

  
eltsFM_GE0 key elt rest elt : rest

  foldFM_GE :: Ord c => (c  ->  b  ->  a  ->  a ->  a  ->  c  ->  FiniteMap c b  ->  a
foldFM_GE k z fr EmptyFM foldFM_GE3 k z fr EmptyFM
foldFM_GE k z fr (Branch key elt vw fm_l fm_rfoldFM_GE2 k z fr (Branch key elt vw fm_l fm_r)

  
foldFM_GE0 k z fr key elt vw fm_l fm_r True foldFM_GE k z fr fm_r

  
foldFM_GE1 k z fr key elt vw fm_l fm_r True foldFM_GE k (k key elt (foldFM_GE k z fr fm_r)) fr fm_l
foldFM_GE1 k z fr key elt vw fm_l fm_r False foldFM_GE0 k z fr key elt vw fm_l fm_r otherwise

  
foldFM_GE2 k z fr (Branch key elt vw fm_l fm_rfoldFM_GE1 k z fr key elt vw fm_l fm_r (key >= fr)

  
foldFM_GE3 k z fr EmptyFM z
foldFM_GE3 wv ww wx wy foldFM_GE2 wv ww wx wy


module Maybe where
  import qualified FiniteMap
import qualified Prelude



Haskell To QDPs


↳ HASKELL
  ↳ LR
    ↳ HASKELL
      ↳ BR
        ↳ HASKELL
          ↳ COR
            ↳ HASKELL
              ↳ Narrow
                ↳ AND
QDP
                    ↳ QDPSizeChangeProof
                  ↳ QDP
                  ↳ QDP
                  ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

new_foldFM_GE1(wz13, LT, wz331, wz332, wz333, wz334, h) → new_foldFM_GE(wz13, wz334, h)
new_foldFM_GE1(wz13, EQ, wz331, wz332, wz333, wz334, h) → new_foldFM_GE(wz13, wz334, h)
new_foldFM_GE1(wz13, GT, wz331, wz332, wz333, wz334, h) → new_foldFM_GE0(wz331, new_foldFM_GE2(wz13, wz334, h), wz333, h)
new_foldFM_GE(wz13, Branch(wz3340, wz3341, wz3342, wz3343, wz3344), h) → new_foldFM_GE1(wz13, wz3340, wz3341, wz3342, wz3343, wz3344, h)
new_foldFM_GE1(wz13, GT, wz331, wz332, wz333, Branch(wz3340, wz3341, wz3342, wz3343, wz3344), h) → new_foldFM_GE1(wz13, wz3340, wz3341, wz3342, wz3343, wz3344, h)
new_foldFM_GE0(wz31, wz7, Branch(wz330, wz331, wz332, wz333, wz334), h) → new_foldFM_GE1(new_eltsFM_GE0(wz31, wz7, h), wz330, wz331, wz332, wz333, wz334, h)

The TRS R consists of the following rules:

new_eltsFM_GE0(wz31, wz7, h) → :(wz31, wz7)
new_foldFM_GE3(wz31, wz7, Branch(wz330, wz331, wz332, wz333, wz334), h) → new_foldFM_GE10(new_eltsFM_GE0(wz31, wz7, h), wz330, wz331, wz332, wz333, wz334, h)
new_foldFM_GE2(wz13, Branch(wz3340, wz3341, wz3342, wz3343, wz3344), h) → new_foldFM_GE10(wz13, wz3340, wz3341, wz3342, wz3343, wz3344, h)
new_foldFM_GE10(wz13, EQ, wz331, wz332, wz333, wz334, h) → new_foldFM_GE2(wz13, wz334, h)
new_foldFM_GE10(wz13, LT, wz331, wz332, wz333, wz334, h) → new_foldFM_GE2(wz13, wz334, h)
new_foldFM_GE10(wz13, GT, wz331, wz332, wz333, wz334, h) → new_foldFM_GE3(wz331, new_foldFM_GE2(wz13, wz334, h), wz333, h)
new_foldFM_GE3(wz31, wz7, EmptyFM, h) → new_eltsFM_GE0(wz31, wz7, h)
new_foldFM_GE2(wz13, EmptyFM, h) → wz13

The set Q consists of the following terms:

new_eltsFM_GE0(x0, x1, x2)
new_foldFM_GE3(x0, x1, EmptyFM, x2)
new_foldFM_GE2(x0, EmptyFM, x1)
new_foldFM_GE10(x0, GT, x1, x2, x3, x4, x5)
new_foldFM_GE3(x0, x1, Branch(x2, x3, x4, x5, x6), x7)
new_foldFM_GE10(x0, EQ, x1, x2, x3, x4, x5)
new_foldFM_GE2(x0, Branch(x1, x2, x3, x4, x5), x6)
new_foldFM_GE10(x0, LT, x1, x2, x3, x4, x5)

We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:



↳ HASKELL
  ↳ LR
    ↳ HASKELL
      ↳ BR
        ↳ HASKELL
          ↳ COR
            ↳ HASKELL
              ↳ Narrow
                ↳ AND
                  ↳ QDP
QDP
                    ↳ QDPSizeChangeProof
                  ↳ QDP
                  ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

new_foldFM_GE4(wz16, Branch(EQ, wz331, wz332, wz333, wz334), h) → new_foldFM_GE4(wz16, wz334, h)
new_foldFM_GE4(wz16, Branch(GT, wz331, wz332, wz333, wz334), h) → new_foldFM_GE4(new_eltsFM_GE0(wz331, new_foldFM_GE5(wz16, wz334, h), h), wz333, h)
new_foldFM_GE4(wz16, Branch(LT, wz331, wz332, wz333, wz334), h) → new_foldFM_GE4(wz16, wz334, h)
new_foldFM_GE4(wz16, Branch(GT, wz331, wz332, wz333, wz334), h) → new_foldFM_GE4(wz16, wz334, h)
new_foldFM_GE4(wz16, Branch(EQ, wz331, wz332, wz333, wz334), h) → new_foldFM_GE4(new_eltsFM_GE00(wz331, new_foldFM_GE5(wz16, wz334, h), h), wz333, h)

The TRS R consists of the following rules:

new_eltsFM_GE0(wz31, wz7, h) → :(wz31, wz7)
new_foldFM_GE5(wz16, Branch(LT, wz331, wz332, wz333, wz334), h) → new_foldFM_GE5(wz16, wz334, h)
new_eltsFM_GE00(wz31, wz6, h) → :(wz31, wz6)
new_foldFM_GE5(wz16, Branch(EQ, wz331, wz332, wz333, wz334), h) → new_foldFM_GE5(new_eltsFM_GE00(wz331, new_foldFM_GE5(wz16, wz334, h), h), wz333, h)
new_foldFM_GE5(wz16, EmptyFM, h) → wz16
new_foldFM_GE5(wz16, Branch(GT, wz331, wz332, wz333, wz334), h) → new_foldFM_GE5(new_eltsFM_GE0(wz331, new_foldFM_GE5(wz16, wz334, h), h), wz333, h)

The set Q consists of the following terms:

new_eltsFM_GE0(x0, x1, x2)
new_foldFM_GE5(x0, EmptyFM, x1)
new_eltsFM_GE00(x0, x1, x2)
new_foldFM_GE5(x0, Branch(GT, x1, x2, x3, x4), x5)
new_foldFM_GE5(x0, Branch(LT, x1, x2, x3, x4), x5)
new_foldFM_GE5(x0, Branch(EQ, x1, x2, x3, x4), x5)

We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:



↳ HASKELL
  ↳ LR
    ↳ HASKELL
      ↳ BR
        ↳ HASKELL
          ↳ COR
            ↳ HASKELL
              ↳ Narrow
                ↳ AND
                  ↳ QDP
                  ↳ QDP
QDP
                    ↳ QDPSizeChangeProof
                  ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

new_foldFM_GE6(wz14, Branch(LT, wz331, wz332, wz333, wz334), h) → new_foldFM_GE6(new_eltsFM_GE01(wz331, new_foldFM_GE7(wz14, wz334, h), h), wz333, h)
new_foldFM_GE6(wz14, Branch(GT, wz331, wz332, wz333, wz334), h) → new_foldFM_GE6(wz14, wz334, h)
new_foldFM_GE6(wz14, Branch(LT, wz331, wz332, wz333, wz334), h) → new_foldFM_GE6(wz14, wz334, h)
new_foldFM_GE6(wz14, Branch(EQ, wz331, wz332, wz333, wz334), h) → new_foldFM_GE6(new_eltsFM_GE00(wz331, new_foldFM_GE7(wz14, wz334, h), h), wz333, h)
new_foldFM_GE6(wz14, Branch(EQ, wz331, wz332, wz333, wz334), h) → new_foldFM_GE6(wz14, wz334, h)
new_foldFM_GE6(wz14, Branch(GT, wz331, wz332, wz333, wz334), h) → new_foldFM_GE6(new_eltsFM_GE0(wz331, new_foldFM_GE7(wz14, wz334, h), h), wz333, h)

The TRS R consists of the following rules:

new_eltsFM_GE0(wz31, wz7, h) → :(wz31, wz7)
new_foldFM_GE7(wz14, Branch(EQ, wz331, wz332, wz333, wz334), h) → new_foldFM_GE7(new_eltsFM_GE00(wz331, new_foldFM_GE7(wz14, wz334, h), h), wz333, h)
new_foldFM_GE7(wz14, Branch(LT, wz331, wz332, wz333, wz334), h) → new_foldFM_GE7(new_eltsFM_GE01(wz331, new_foldFM_GE7(wz14, wz334, h), h), wz333, h)
new_eltsFM_GE00(wz31, wz6, h) → :(wz31, wz6)
new_foldFM_GE7(wz14, EmptyFM, h) → wz14
new_eltsFM_GE01(wz31, wz15, h) → :(wz31, wz15)
new_foldFM_GE7(wz14, Branch(GT, wz331, wz332, wz333, wz334), h) → new_foldFM_GE7(new_eltsFM_GE0(wz331, new_foldFM_GE7(wz14, wz334, h), h), wz333, h)

The set Q consists of the following terms:

new_eltsFM_GE01(x0, x1, x2)
new_eltsFM_GE0(x0, x1, x2)
new_foldFM_GE7(x0, Branch(GT, x1, x2, x3, x4), x5)
new_foldFM_GE7(x0, EmptyFM, x1)
new_eltsFM_GE00(x0, x1, x2)
new_foldFM_GE7(x0, Branch(EQ, x1, x2, x3, x4), x5)
new_foldFM_GE7(x0, Branch(LT, x1, x2, x3, x4), x5)

We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:



↳ HASKELL
  ↳ LR
    ↳ HASKELL
      ↳ BR
        ↳ HASKELL
          ↳ COR
            ↳ HASKELL
              ↳ Narrow
                ↳ AND
                  ↳ QDP
                  ↳ QDP
                  ↳ QDP
QDP
                    ↳ QDPSizeChangeProof

Q DP problem:
The TRS P consists of the following rules:

new_foldFM_GE8(GT, Branch(EQ, wz31, wz32, wz33, wz34), h) → new_foldFM_GE8(GT, wz34, h)
new_foldFM_GE8(GT, Branch(GT, wz31, wz32, wz33, wz34), h) → new_foldFM_GE8(GT, wz34, h)
new_foldFM_GE8(GT, Branch(LT, wz31, wz32, wz33, wz34), h) → new_foldFM_GE8(GT, wz34, h)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs: